package me.mingshan.algorithm.lru;


import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * LRU缓存
 *
 * LRU Cache（Least Recently Used的缩写，即最近最少使用，是一种常见的缓存淘汰算法。
 *
 * Cache的容量有限，因此当Cache的容量用完后，而又有新的内容需要添加进来时，
 * 就需要挑选并舍弃原有 的部分内容，从而腾出空间来放新内容。LRU Cache 的替换原则就是将最近最少使用的内容替换掉。
 *
 * 使用双向链表是因为双向链表可以实现任意位置O(1)的插入和删除，双向链表用于记录数据对象的访问顺序，
 * 每当一个数据对象被访问时，就将其移动到链表的头部。这样，链表头部的数据对象就是最近被访问的数据，
 * 而链表尾部的数据对象则是最久未被访问的数据。同时，使用哈希表能够以 O(1) 的时间复杂度进行数据对象的查找。
 *
 * 新访问数据移到链表头，淘汰链表尾数据。
 *
 * 链表 + LinkedHashMap
 *
 * @author mingshan
 */
public class LRUCache {
    private static final int DEFAULT_CAPACITY = 16;

    private final Map<Integer, Integer> map;
    private final LinkedList<Integer> queue;

    private final int capacity;

    public LRUCache() {
        this(DEFAULT_CAPACITY);
    }

    public LRUCache(int capacity) {
        if (capacity <= 0) {
            throw new IllegalArgumentException("capacity <= 0");
        }
        this.map = new HashMap<>();
        this.queue = new LinkedList<>();
        this.capacity = capacity;
    }

    public void put(int key, int value) {
        // 首先判断当前数据是否存在
        if (!map.containsKey(key)) {
            queue.addFirst(key);
        } else {
            // 如果是修改，则需要将其移动到头部
            moveToHead(key);
        }

        map.put(key, value);
        // 如果不存在，首先判断队列中是否已经满了
        if (queue.size() > capacity) {
            // 移除队列中最后一个结点
            map.remove(queue.removeLast());
        }
    }

    public int get(int key) {
        if (map.containsKey(key)) {
            // 如果是修改，则需要将其移动到头部
            int value = map.get(key);
            moveToHead(key);
            return value;
        } else {
            return -1;
        }
    }

    private void moveToHead(int key) {
        queue.remove(Integer.valueOf(key));
        queue.addFirst(Integer.valueOf(key));
    }
}
